package a1PodziemneMuzeum;

import java.io.*;
import java.util.Scanner;

public class Zad1 {

    public static void fun1(String str) {
        if (str.length() > 1) {
            fun1(str.substring(1));
        }
        System.out.print(str.charAt(0));
    }
    static int kosztyPrzejsc[][];
    static int tablicaPrzejsc[][];
    static int ceny[][];

    public static void zerujKoszty(int iloscWierszy, int iloscKolumn) {
        for (int i = 1; i <= iloscWierszy; i++) {
            for (int j = 1; j <= iloscKolumn; j++) {
                kosztyPrzejsc[i][j] = -1;
            }
        }
    }

    public static void zerujTablicePrzejsc(int iloscWierszy, int iloscKolumn) {
        for (int i = 1; i <= iloscWierszy; i++) {
            for (int j = 1; j <= iloscKolumn; j++) {
                tablicaPrzejsc[i][j] = 0;
            }
        }
        tablicaPrzejsc[iloscWierszy][1] = 1;
        tablicaPrzejsc[1][iloscKolumn] = 1;
    }

    public static void wypiszKoszty(int iloscWierszy, int iloscKolumn) {
        for (int i = 1; i <= iloscWierszy; i++) {
            for (int j = 1; j <= iloscKolumn; j++) {
                System.out.print(kosztyPrzejsc[i][j] + " ");
            }
            System.out.println("");
        }
    }

    public static void wypiszTablicePrzejsc(int iloscWierszy, int iloscKolumn) {
        for (int i = 1; i <= iloscWierszy; i++) {
            for (int j = 1; j <= iloscKolumn; j++) {
                System.out.print(tablicaPrzejsc[i][j] + " ");
            }
            System.out.println("");
        }
    }

    public static int wypiszPrzejscia(int tablicaPrzejsc[][], int iloscWierszy, int iloscKolumn) {
        int licznik = 0;
        for (int i = 1; i <= iloscWierszy; i++) {
            for (int j = 1; j <= iloscKolumn; j++) {
                licznik = licznik + tablicaPrzejsc[i][j];
            }
        }
        return licznik;
    }

    public static void main(String[] args) throws IOException {
        Scanner S = new Scanner(new File("C:\\Users\\Adam\\Desktop\\programowanie\\ASD1\\src\\a1PodziemneMuzeum\\daneMuzeum.txt"));
        int iloscWierszy = S.nextInt();
        int iloscKolumn = S.nextInt();
        kosztyPrzejsc = new int[iloscWierszy + 1][iloscKolumn + 1];
        tablicaPrzejsc = new int[iloscWierszy + 1][iloscKolumn + 1];
        zerujTablicePrzejsc(iloscWierszy, iloscKolumn);
        ceny = new int[iloscWierszy + 1][iloscKolumn + 1];

        for (int i = 1; i <= iloscWierszy; i++) {
            for (int j = 1; j <= iloscKolumn; j++) {
                ceny[i][j] = S.nextInt();
            }
        }
        int x = 1;
        int y = 1;
        while (x + y != 0) {
            Kopiec kopiec = new Kopiec(3 * iloscKolumn * iloscWierszy);
            x = S.nextInt();
            y = S.nextInt();
            //kosztyPrzejsc[x][y]=ceny[x][y];
            if (x + y != 0) {
                kopiec.wstaw(new Sala(ceny[x][y], x, y));
            } else {
                kopiec.wstaw(new Sala(ceny[iloscWierszy][1], iloscWierszy, 1));
            }
            zerujKoszty(iloscWierszy, iloscKolumn);
            while (kosztyPrzejsc[1][iloscKolumn] == -1 || kosztyPrzejsc[iloscWierszy][1] == -1) {
                Sala obecna = kopiec.zabierz();
                if (kosztyPrzejsc[obecna.x][obecna.y] == -1) {
                    kosztyPrzejsc[obecna.x][obecna.y] = obecna.cena;
                    if (obecna.x + 1 <= iloscWierszy && kosztyPrzejsc[obecna.x + 1][obecna.y] == -1) {
                        kopiec.wstaw(new Sala(obecna.cena + ceny[obecna.x + 1][obecna.y], obecna.x + 1, obecna.y));
                    }
                    if (obecna.x - 1 > 0 && kosztyPrzejsc[obecna.x - 1][obecna.y] == -1) {
                        kopiec.wstaw(new Sala(obecna.cena + ceny[obecna.x - 1][obecna.y], obecna.x - 1, obecna.y));
                    }
                    if (obecna.y + 1 <= iloscKolumn && kosztyPrzejsc[obecna.x][obecna.y + 1] == -1) {
                        kopiec.wstaw(new Sala(obecna.cena + ceny[obecna.x][obecna.y + 1], obecna.x, obecna.y + 1));
                    }
                    if (obecna.y - 1 > 0 && kosztyPrzejsc[obecna.x][obecna.y - 1] == -1) {
                        kopiec.wstaw(new Sala(obecna.cena + ceny[obecna.x][obecna.y - 1], obecna.x, obecna.y - 1));
                    }
                }
            }
            String kierunki = "";
            String kierunkiOdKonca = "";

            int X = iloscWierszy;
            int Y = 1;
            if (x + y != 0) {
                System.out.print(kosztyPrzejsc[iloscWierszy][1] + kosztyPrzejsc[1][iloscKolumn] - ceny[x][y] + " ");
                kierunki = "";
                kierunkiOdKonca = "";
                X = iloscWierszy;
                Y = 1;
                while (X != x || Y != y) {
                    Kopiec Sale = new Kopiec(5);
                    if (X + 1 <= iloscWierszy && kosztyPrzejsc[X + 1][Y] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X + 1][Y], X + 1, Y));
                    }
                    if (X - 1 > 0 && kosztyPrzejsc[X - 1][Y] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X - 1][Y], X - 1, Y));
                    }
                    if (Y + 1 <= iloscKolumn && kosztyPrzejsc[X][Y + 1] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X][Y + 1], X, Y + 1));
                    }
                    if (Y - 1 > 0 && kosztyPrzejsc[X][Y - 1] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X][Y - 1], X, Y - 1));
                    }
                    Sala zabrana = Sale.zabierz();
                    int zabranyX = zabrana.x;
                    int zabranyY = zabrana.y;
                    if (zabranyX > X) {
                        kierunki = kierunki + "S";
                        tablicaPrzejsc[X + 1][Y] = 1;
                    }
                    if (zabranyX < X) {
                        kierunki = kierunki + "N";
                        tablicaPrzejsc[X - 1][Y] = 1;
                    }
                    if (zabranyY > Y) {
                        kierunki = kierunki + "E";
                        tablicaPrzejsc[X][Y + 1] = 1;
                    }
                    if (zabranyY < Y) {
                        kierunki = kierunki + "W";
                        tablicaPrzejsc[X][Y - 1] = 1;
                    }
                    X = zabranyX;
                    Y = zabranyY;
                }
                X = 1;
                Y = iloscKolumn;
                while (X != x || Y != y) {
                    Kopiec Sale = new Kopiec(5);
                    if (X + 1 <= iloscWierszy && kosztyPrzejsc[X + 1][Y] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X + 1][Y], X + 1, Y));
                    }
                    if (X - 1 > 0 && kosztyPrzejsc[X - 1][Y] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X - 1][Y], X - 1, Y));
                    }
                    if (Y + 1 <= iloscKolumn && kosztyPrzejsc[X][Y + 1] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X][Y + 1], X, Y + 1));
                    }
                    if (Y - 1 > 0 && kosztyPrzejsc[X][Y - 1] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X][Y - 1], X, Y - 1));
                    }
                    Sala zabrana = Sale.zabierz();
                    int zabranyX = zabrana.x;
                    int zabranyY = zabrana.y;
                    if (zabranyX > X) {
                        kierunkiOdKonca = kierunkiOdKonca + "N";
                        tablicaPrzejsc[X + 1][Y] = 1;
                    }
                    if (zabranyX < X) {
                        kierunkiOdKonca = kierunkiOdKonca + "S";
                        tablicaPrzejsc[X - 1][Y] = 1;
                    }
                    if (zabranyY > Y) {
                        kierunkiOdKonca = kierunkiOdKonca + "W";
                        tablicaPrzejsc[X][Y + 1] = 1;
                    }
                    if (zabranyY < Y) {
                        kierunkiOdKonca = kierunkiOdKonca + "E";
                        tablicaPrzejsc[X][Y - 1] = 1;
                    }
                    X = zabranyX;
                    Y = zabranyY;
                }
                System.out.print(wypiszPrzejscia(tablicaPrzejsc, iloscWierszy, iloscKolumn) + " ");

                zerujTablicePrzejsc(iloscWierszy, iloscKolumn);
                System.out.print(kierunki);
                fun1(kierunkiOdKonca);
                System.out.println("");

            } else {
                System.out.print(kosztyPrzejsc[1][iloscKolumn] + " ");
                kierunkiOdKonca = "";

                X = 1;
                Y = iloscKolumn;
                x = iloscWierszy;
                y = 1;
                while (X != x || Y != y) {
                    Kopiec Sale = new Kopiec(5);
                    if (X + 1 <= iloscWierszy && kosztyPrzejsc[X + 1][Y] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X + 1][Y], X + 1, Y));
                    }
                    if (X - 1 > 0 && kosztyPrzejsc[X - 1][Y] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X - 1][Y], X - 1, Y));
                    }
                    if (Y + 1 <= iloscKolumn && kosztyPrzejsc[X][Y + 1] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X][Y + 1], X, Y + 1));
                    }
                    if (Y - 1 > 0 && kosztyPrzejsc[X][Y - 1] != -1) {
                        Sale.wstaw(new Sala(kosztyPrzejsc[X][Y - 1], X, Y - 1));
                    }
                    Sala zabrana = Sale.zabierz();
                    int zabranyX = zabrana.x;
                    int zabranyY = zabrana.y;
                    if (zabranyX > X) {
                        kierunkiOdKonca = kierunkiOdKonca + "N";
                        tablicaPrzejsc[X + 1][Y] = 1;
                    }
                    if (zabranyX < X) {
                        kierunkiOdKonca = kierunkiOdKonca + "S";
                        tablicaPrzejsc[X - 1][Y] = 1;
                    }
                    if (zabranyY > Y) {
                        kierunkiOdKonca = kierunkiOdKonca + "W";
                        tablicaPrzejsc[X][Y + 1] = 1;
                    }
                    if (zabranyY < Y) {
                        kierunkiOdKonca = kierunkiOdKonca + "E";
                        tablicaPrzejsc[X][Y - 1] = 1;
                    }
                    X = zabranyX;
                    Y = zabranyY;
                }
                System.out.print(wypiszPrzejscia(tablicaPrzejsc, iloscWierszy, iloscKolumn) + " ");
                fun1(kierunkiOdKonca);
                x = 0;
                y = 0;
            }

        }
        System.out.println("");
    }
}